home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 March / EnigmA AMIGA RUN 05 (1996)(G.R. Edizioni)(IT)[!][issue 1996-03][Skylink CD IV].iso / earcd / program / ixemlsrc.lha / ixemul / network / btree.h < prev    next >
C/C++ Source or Header  |  1995-12-23  |  11KB  |  331 lines
  1. #ifndef _BTREE_H_
  2. #define _BTREE_H_
  3.  
  4. /*-
  5.  * Copyright (c) 1990 The Regents of the University of California.
  6.  * All rights reserved.
  7.  *
  8.  * This code is derived from software contributed to Berkeley by
  9.  * Mike Olson.
  10.  *
  11.  * Redistribution and use in source and binary forms, with or without
  12.  * modification, are permitted provided that the following conditions
  13.  * are met:
  14.  * 1. Redistributions of source code must retain the above copyright
  15.  *    notice, this list of conditions and the following disclaimer.
  16.  * 2. Redistributions in binary form must reproduce the above copyright
  17.  *    notice, this list of conditions and the following disclaimer in the
  18.  *    documentation and/or other materials provided with the distribution.
  19.  * 3. All advertising materials mentioning features or use of this software
  20.  *    must display the following acknowledgement:
  21.  *    This product includes software developed by the University of
  22.  *    California, Berkeley and its contributors.
  23.  * 4. Neither the name of the University nor the names of its contributors
  24.  *    may be used to endorse or promote products derived from this software
  25.  *    without specific prior written permission.
  26.  *
  27.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  28.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  31.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37.  * SUCH DAMAGE.
  38.  */
  39.  
  40. /*
  41.  *  @(#)btree.h    5.2 (Berkeley) 2/22/91
  42.  */
  43.  
  44. typedef char    *BTREE;        /* should really be (void *) */ 
  45.  
  46. /* #define    DEBUG */
  47.  
  48. #define RET_ERROR    -1
  49. #define RET_SUCCESS     0
  50. #define RET_SPECIAL     1
  51.  
  52. #ifndef TRUE
  53. #define TRUE    1
  54. #define FALSE    0
  55. #endif /* ndef TRUE */
  56.  
  57. #ifndef NULL
  58. #define NULL    0
  59. #endif /* ndef NULL */
  60.  
  61. /* these are defined in lrucache.c */
  62. extern char    *lruinit();
  63. extern char    *lruget();
  64. extern char    *lrugetnew();
  65. extern int    lrusync();
  66. extern int    lruwrite();
  67. extern int    lrurelease();
  68. extern void    lrufree();
  69.  
  70. /* these are defined here */
  71. extern BTREE    bt_open();
  72. extern int    bt_close();
  73. extern int    bt_delete();
  74. extern int    bt_get();
  75. extern int    bt_put();
  76. extern int    bt_seq();
  77. extern int    bt_sync();
  78.  
  79. /*
  80.  *  Private types.  What you choose for these depends on how big you
  81.  *  want to let files get, and how big you want to let pages get.
  82.  */
  83.  
  84. typedef u_long    index_t;    /* so # bytes on a page fits in a long */
  85. typedef u_long    pgno_t;        /* so # of pages in a btree fits in a long */
  86.  
  87. /*
  88.  *  When we do searches, we push the parent page numbers onto a stack
  89.  *  as we descend the tree.  This is so that for insertions, we can
  90.  *  find our way back up to do internal page insertions and splits.
  91.  */
  92.  
  93. typedef struct BTSTACK {
  94.     pgno_t        bts_pgno;
  95.     struct BTSTACK    *bts_next;
  96. } BTSTACK;
  97.  
  98. /*
  99.  *  Every btree page has a header that looks like this.  Flags are given
  100.  *  in the #define's for the F_ flags (see below).
  101.  */
  102.  
  103. typedef struct BTHEADER {
  104.     pgno_t h_pgno;        /* page number of this page */
  105.     pgno_t h_prevpg;    /* left sibling */
  106.     pgno_t h_nextpg;    /* right sibling */
  107.  
  108. #define F_LEAF        0x01    /* leaf page, contains user data */
  109. #define F_CONT        0x02    /* continuation page (large items) */
  110. #define F_DIRTY        0x04    /* need to write to disk */
  111. #define F_PRESERVE    0x08    /* never delete this chain of pages */
  112.  
  113.     u_long h_flags;        /* page state */
  114.     index_t h_lower;    /* lower bound of free space on page */
  115.     index_t h_upper;    /* upper bound of free space on page */
  116.     index_t h_linp[1];    /* VARIABLE LENGTH DATA AT END OF STRUCT */
  117. } BTHEADER;
  118.  
  119. /*
  120.  *  HTBUCKETs are hash table buckets for looking up pages of in-memory
  121.  *  btrees by page number.  We use this indirection, rather than direct
  122.  *  pointers, so that the code for manipulating in-memory trees is the
  123.  *  same as that for manipulating on-disk trees.
  124.  */
  125.  
  126. typedef struct HTBUCKET {
  127.     pgno_t        ht_pgno;
  128.     BTHEADER    *ht_page;
  129.     struct HTBUCKET    *ht_next;
  130. } HTBUCKET;
  131.  
  132. typedef HTBUCKET    **HTABLE;
  133.  
  134. /* minimum size we'll let a page be */
  135. #define MINPSIZE    512
  136.  
  137. /* default cache size, in bytes */
  138. #define DEFCACHE    (20 * 1024)
  139.  
  140. /* hash table size for in-memory trees */
  141. #define    HTSIZE        128
  142.  
  143. /* generate a hash key from a page number */
  144. #define HASHKEY(pgno)    ((pgno - 1) % HTSIZE)
  145.  
  146. /*
  147.  *  Disk btrees have a file descriptor, and may also have an lru buffer
  148.  *  cache, if the user asked for one.
  149.  */
  150.  
  151. typedef struct BTDISK {
  152.     int    d_fd;
  153.     char    *d_cache;
  154. } BTDISK;
  155.  
  156. /*
  157.  *  Cursors keep track of the current location in a sequential scan of
  158.  *  the database.  Since btrees impose a total ordering on keys, we can
  159.  *  walk forward or backward through the database from any point.  Cursors
  160.  *  survive updates to the tree, and can be used to delete a particular
  161.  *  record.
  162.  */
  163.  
  164. typedef struct CURSOR {
  165.     pgno_t        c_pgno;        /* pgno of current item in scan */
  166.     index_t        c_index;    /* index of current item in scan */
  167.     char        *c_key;        /* current key, used for updates */
  168.  
  169. #define CRSR_BEFORE    0x01
  170.  
  171.     u_char        c_flags;    /* to handle updates properly */
  172. } CURSOR;
  173.  
  174. /*
  175.  *  The private btree data structure.  The user passes a pointer to one of
  176.  *  these when we are to manipulate a tree, but the BTREE type is opaque
  177.  *  to him.
  178.  */
  179.  
  180. typedef struct BTREEDATA_P {
  181.     char        *bt_fname;        /* NULL for in-memory trees */
  182.     union {
  183.         BTDISK    bt_d;            /* for on-disk btrees */
  184.         HTABLE    bt_ht;            /* hash table for mem trees */
  185.     } bt_s;
  186.     size_t        bt_psize;        /* page size for btree pages */
  187.     int        (*bt_compare)();    /* key comparison function */
  188.     pgno_t        bt_npages;        /* number of pages in tree */
  189.     BTHEADER    *bt_curpage;        /* current page contents */
  190.     pgno_t        bt_free;        /* free pg list for big data */
  191.     CURSOR        bt_cursor;        /* cursor for scans */
  192.     BTSTACK        *bt_stack;        /* parent stack for inserts */
  193.     u_long        bt_lorder;        /* byte order (endian.h) */
  194.  
  195. #define BTF_METAOK    0x01    /* meta-data written to start of file */
  196. #define BTF_SEQINIT    0x02    /* we have called bt_seq */
  197. #define BTF_ISWRITE    0x04    /* tree was opened for write */
  198. #define BTF_NODUPS    0x08    /* tree created for unique keys */
  199.  
  200.     u_long        bt_flags;        /* btree state */
  201. } BTREEDATA_P;
  202.  
  203. typedef BTREEDATA_P    *BTREE_P;
  204.  
  205. /*
  206.  *  The first thing in a btree file is a BTMETA structure.  The rest of
  207.  *  the first page is empty, so that all disk operations are page-aligned.
  208.  */
  209.  
  210. typedef struct BTMETA {
  211.     u_long    m_magic;
  212.     u_long    m_version;
  213.     size_t    m_psize;
  214.     pgno_t    m_free;
  215.     u_long    m_flags;
  216.     u_long    m_lorder;
  217. } BTMETA;
  218.  
  219. #define P_NONE        0        /* invalid page number in tree */
  220. #define P_ROOT        1        /* page number of root pg in btree */
  221.  
  222. #define NORELEASE    0        /* don't release a page during write */
  223. #define RELEASE        1        /* release a page during write */
  224.  
  225. #define INSERT        0        /* doing an insert operation */
  226. #define DELETE        1        /* doing a delete operation */
  227.  
  228. /* get the next free index on a btree page */
  229. #define NEXTINDEX(p)    ((((int)(p)->h_lower) - ((int)((((char *)(&(p)->h_linp[0]))) - ((char *) (p)))))/(sizeof(index_t)))
  230.  
  231. /* is a BTITEM actually on the btree page? */
  232. #define VALIDITEM(t, i)    ((i)->bti_index < NEXTINDEX((t)->bt_curpage))
  233.  
  234. /* guarantee longword alignment so structure refs work */
  235. #define LONGALIGN(p) (((long)(p) + 3) & ~ 0x03)
  236.  
  237. /* get a particular datum (or idatum) off a page */
  238. #define GETDATUM(h,i)     (((char *) h) + h->h_linp[i])
  239.  
  240. /* is a {key,datum} too big to put on a single page? */
  241. #define TOOBIG(t, sz)    (sz >= t->bt_psize / 5)
  242.  
  243. /* is this a disk tree or a memory tree? */
  244. #define ISDISK(t)    (t->bt_fname != (char *) NULL)
  245.  
  246. /* does the disk tree use a cache? */
  247. #define ISCACHE(t)    (t->bt_s.bt_d.d_cache != (char *) NULL)
  248.  
  249. /*
  250.  *  DATUMs are for user data -- one appears on leaf pages for every
  251.  *  tree entry.  The d_bytes[] array contains the key first, then the data.
  252.  *
  253.  *  If either the key or the datum is too big to store on a single page,
  254.  *  a bit is set in the flags entry, and the d_bytes[] array contains a
  255.  *  pgno pointing to the page at which the data is actually stored.
  256.  *
  257.  *  Note on alignment:  every DATUM is guaranteed to be longword aligned
  258.  *  on the disk page.  In order to force longword alignment of user key
  259.  *  and data values, we must guarantee that the d_bytes[] array starts
  260.  *  on a longword boundary.  This is the reason that d_flags is a u_long,
  261.  *  rather than a u_char (it really only needs to be two bits big).  This
  262.  *  is necessary because we call the user's comparison function with a
  263.  *  pointer to the start of the d_bytes array.  We don't need to force
  264.  *  longword alignment of the data following the key, since that is copied
  265.  *  to a longword-aligned buffer before being returned to the user.
  266.  */
  267.  
  268. typedef struct DATUM {
  269.     size_t d_ksize;        /* size of key */
  270.     size_t d_dsize;        /* size of data */
  271.  
  272. #define D_BIGDATA    0x01    /* indirect datum ptr flag */
  273. #define D_BIGKEY    0x02    /* indirect key ptr flag */
  274.  
  275.     u_long d_flags;        /* flags (indirect bit) */
  276.     char d_bytes[1];    /* VARIABLE LENGTH DATA AT END OF STRUCT */
  277. } DATUM;
  278.  
  279. /* BTITEMs are used to return (page, index, datum) tuples from searches */
  280. typedef struct BTITEM {
  281.     pgno_t bti_pgno;
  282.     index_t bti_index;
  283.     DATUM *bti_datum;
  284. } BTITEM;
  285.  
  286. /*
  287.  *  IDATUMs are for data stored on internal pages.  This is the (key, pgno)
  288.  *  pair, such that key 'key' is the first entry on page 'pgno'.  If our
  289.  *  internal page contains keys (a) and (b) next to each other, then all
  290.  *  items >= to (a) and < (b) go on the same page as (a).  There are some
  291.  *  gotchas with duplicate keys, however.  See the split code for details.
  292.  *
  293.  *  If a key is too big to fit on a single page, then the i_bytes[] array
  294.  *  contains a pgno pointing to the start of a chain that actually stores
  295.  *  the bytes.  Since items on internal pages are never deleted from the
  296.  *  tree, these indirect chains are marked as special, so that they won't
  297.  *  be deleted if the corresponding leaf item is deleted.
  298.  *
  299.  *  As for DATUMs, IDATUMs have a u_long flag entry (rather than u_char)
  300.  *  in order to guarantee that user keys are longword aligned on the disk
  301.  *  page.
  302.  */
  303.  
  304. typedef struct IDATUM {
  305.     size_t i_size;
  306.     pgno_t i_pgno;
  307.     u_long i_flags;        /* see DATUM.d_flags, above */
  308.     char i_bytes[1];    /* VARIABLE LENGTH DATA AT END OF STRUCT */
  309. } IDATUM;
  310.  
  311. /* all private interfaces have a leading _ in their names */
  312. extern BTITEM    *_bt_search();
  313. extern BTITEM    *_bt_searchr();
  314. extern BTHEADER    *_bt_allocpg();
  315. extern index_t    _bt_binsrch();
  316. extern int    _bt_isonpage();
  317. extern BTITEM    *_bt_first();
  318. extern int    _bt_release();
  319. extern int    _bt_wrtmeta();
  320. extern int    _bt_delindir();
  321. extern int    _bt_pgout();
  322. extern int    _bt_pgin();
  323. extern int    _bt_fixscan();
  324. extern int    _bt_indirect();
  325. extern int    _bt_crsrdel();
  326. extern int    _bt_push();
  327. extern pgno_t    _bt_pop();
  328. extern int    strcmp();
  329.  
  330. #endif
  331.